package com.zk.algorithm;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 字符串工具
 *
 * @author zk
 */
public final class StringUtils {

    /**
     * 构建后缀数组（排序后的）
     *
     * @param s
     * @return
     */
    public static final int[] buildSufficArray(String s) {
        List<Wrapper> subStringList = buildSufficArrayWrapper(s);
        return subStringList.stream().mapToInt(w -> w.index).toArray();
    }

    /**
     * 构建高度数组 (后缀数组中相邻两个后缀的最长公共前缀的长度组成的数组)
     *
     * @param s
     * @return
     */
    public static final int[] buildLongestCommonPrefixArray(String s) {
        List<Wrapper> subStringList = buildSufficArrayWrapper(s);

        int[] lcp = new int[subStringList.size() - 1];

        for (int i = 1; i < subStringList.size(); i++) {
            lcp[i - 1] = calcLongestCommonPrefixLength(subStringList.get(i), subStringList.get(i - 1));
        }

        return lcp;
    }

    private static int calcLongestCommonPrefixLength(Wrapper a, Wrapper b) {
        int size = Math.min(a.s.length(), b.s.length());
        int index = 0;
        int length = 0;

        while (index < size) {
            if (a.s.charAt(index) != b.s.charAt(index)) {
                break;
            }

            index++;
            length++;
        }

        return length;
    }

    private static final List<Wrapper> buildSufficArrayWrapper(String s) {
        List<Wrapper> subStringList = new ArrayList<>();

        for (int i = 0; i < s.length(); i++) {
            subStringList.add(new Wrapper(s.substring(i), i));
        }

        Collections.sort(subStringList);

        return subStringList;
    }

    private static class Wrapper implements Comparable<Wrapper> {

        final String s;
        final int index;

        public Wrapper(String s, int index) {
            this.s = s;
            this.index = index;
        }

        @Override
        public int compareTo(Wrapper o) {
            return s.compareTo(o.s);
        }

    }

}
